package main

import "fmt"
/*
	有效的完全平方数
给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。
进阶：不要 使用任何内置的库函数，如  sqrt 。


示例 1：
输入：num = 16
输出：true

示例 2：
输入：num = 14
输出：false
 */

// 二分法
// 每次对num右移  判断它的平方与num的大小
// 三种情况
// 等于  直接返回true
// 大于  继续右移
// 小于  遍历当前数与它左移后的数之间  并判断与num是否相等
func isPerfectSquare(num int) bool {
	if num == 1 {
		return true
	}
	temp := num >> 1
	for {
		mul := temp * temp
		if mul == num {
			return true
		}else if mul > num {
			temp = temp >> 1
		}else {
			break
		}
	}
	for i := temp + 1; i <= temp << 1; i ++ {
		if i * i == num {
			return true
		}
	}
	return false
}

// 方法二  数学方法
// 1 , 4 = 1 + 3 , 9 = 1 + 3 + 5.......每次减去一个奇数，最后若为0 则为true否则为false
func isPerfectSquare2(num int) bool {
	num1 := 1
	for num > 0 {
		num -= num1
		num1 += 2   // 奇数
	}
	if num == 0 {
		return true
	}else{
		return false
	}
}

func main() {
	fmt.Println(isPerfectSquare(17))
}
